﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace WordNet.Core.Graph
{
    public class FindAncestor : IFindAncestor
    {
        private const int MAX_DISTANCE = int.MaxValue;
        private Dictionary<int, bool> _marked;
        private Dictionary<int, int> _edgeTo;
        private Dictionary<int, int> _distTo;
        private int _ancestor;
        private int _pathLength;
        private IDigraph _g;

        public FindAncestor(IDigraph g, int v, IShortestPath path)
        {
            _g = g;
            Init();
            Search(v, path);
        }
       
        public FindAncestor(IDigraph g, IEnumerable<int> sources, IShortestPath path)
        {
            _g = g;
            Init();
            Search(sources, path);
        }
        
        private void Init()
        {
            _marked = new Dictionary<int, bool>(_g.NumberOfVertices);
            _edgeTo = new Dictionary<int, int>(_g.NumberOfVertices);
            _distTo = new Dictionary<int, int>(_g.NumberOfVertices);
            foreach (var v in _g.GetAllVertices())
            {
                _distTo.Add(v, MAX_DISTANCE);
                _marked.Add(v, false);
                _edgeTo.Add(v, 0);
            }
        }
        
        private void Search(IEnumerable<int> sources, IShortestPath path)
        {
            Queue<int> q = new Queue<int>();
            int current_minLenOfPath = MAX_DISTANCE;
            int current_ancestor = -1;
            foreach (int item in sources)
            {
                _marked[item] = true;
                _distTo[item] = 0;
                q.Enqueue(item);
            }

            while (q.Count() > 0)
            {
                int temp = q.Dequeue();

                // find if current node is ancestor
                if (path.HasPathTo(temp) &&
                   _distTo[temp] + path.DistanceTo(temp) < current_minLenOfPath)
                {
                    current_minLenOfPath = (_distTo[temp] + path.DistanceTo(temp));
                    current_ancestor = temp;
                }

                // navigate the path
                if (path.DistanceTo(temp) > 0)
                {
                    foreach (int item in _g.AdjacencyList(temp))
                    {
                        if (!_marked[item])
                        {
                            _edgeTo[item] = temp;
                            _marked[item] = true;
                            _distTo[item] = _distTo[temp] + 1;
                            q.Enqueue(item);
                        }
                    }
                }
            }
            _ancestor = current_ancestor;
            _pathLength = (current_minLenOfPath == MAX_DISTANCE) ?
                                                    -1 :
                                                    current_minLenOfPath;
        }

        private void Search(int v, IShortestPath path)
        {
            Queue<int> q = new Queue<int>();
            _distTo[v] = 0;
            _marked[v] = true;
            q.Enqueue(v);
            int current_minLenOfPath = MAX_DISTANCE;
            int current_ancestor = -1;
            while (q.Count() > 0)
            {
                int temp = q.Dequeue();

                // find if current node is ancestor
                if (path.HasPathTo(temp) &&
                   _distTo[temp] + path.DistanceTo(temp) < current_minLenOfPath)
                {
                    current_minLenOfPath = (_distTo[temp] + path.DistanceTo(temp));
                    current_ancestor = temp;
                }

                // navigate the path
                if (path.DistanceTo(temp) > 0)
                {
                    foreach (int item in _g.AdjacencyList(temp))
                    {
                        if (!_marked[item])
                        {
                            _edgeTo[item] = temp;
                            _marked[item] = true;
                            _distTo[item] = _distTo[temp] + 1;
                            q.Enqueue(item);
                        }
                    }
                }
            }
            _ancestor = current_ancestor;
            _pathLength = (current_minLenOfPath == MAX_DISTANCE) ?
                                                   -1 :
                                                   current_minLenOfPath;
        }

        public bool HasPathTo(int vertex)
        {
            return _marked[vertex];
        }

        public int Ancestor
        {
            get { return _ancestor; ; }
        }

        public int PathLength
        {
            get { return _pathLength; }
        }
    }
}
